# 宝石收集(好题, 考虑tarjan算法找到强连通分量并缩点)
# 2025/3/4
from collections import defaultdict


def tarjan_scc(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    index = 0
    stack = []
    disc = [-1] * n  # 时间戳, 记录每个节点的发现时间
    low = [-1] * n  # 与可以回溯的最早节点
    on_stack = [False] * n  # visited, 用于检查节点是否已经访问过
    sccs = []

    def strong_connect(v):
        nonlocal index, stack, low, disc, on_stack, sccs
        disc[v] = low[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        # 遍历邻接点
        for w in graph[v]:
            if disc[w] == -1:  # 如果w节点从没访问过，则先访问它，再用它更新low[v]的值
                strong_connect(w)
                low[v] = min(low[v], low[w])  # 如果节点w可以连到更小的祖先节点，显然其父节点v也可以
            elif on_stack[w]:  # 如果w节点已经访问过, 并且w也在栈中, 那么更新节点v的low值
                low[v] = min(low[v], disc[w])


        if low[v] == disc[v]:  # 如果 u 是 SCC 的根节点, 即如果一个节点的low和disc相同, 则它必然是该强连通分量的根节点
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:  # 将栈中的数据弹出, 由于栈的filo属性, 该强联通分量的最早节点必然是最先入栈的
                    break
            sccs.append(scc)

    for v in range(n):
        if disc[v] == -1:
            strong_connect(v)

    return sccs


def max_purple_gems(n, category, edges):
    """利用Tarjan算法计算强联通分量,并缩点
    强联通分量(Strongly Connected Components, SCCs): 在有向图中的一个子图，其中每两个顶点互相可达。
    缩点: 将所有强连通分量看做一个节点
    """
    sccs = tarjan_scc(n, edges)

    scc_id = {}  # 记录每个节点属于哪个SCC
    scc_category = []  # 记录每个SCC内红蓝宝石的数量

    # 统计每个SCC内的红蓝宝石的数量
    for i, scc in enumerate(sccs):
        red, blue = 0, 0
        for node in scc:
            scc_id[node] = i
            if category[node] == 0:
                red += 1
            else:
                blue += 1
        scc_category.append((red, blue))

    scc_graph = defaultdict(set)  # 构建缩点后的DAG
    for u, v in edges:
        if scc_id[u] != scc_id[v]:  # 如果u和v不在同一个强连通分量中则构建这个边
            scc_graph[scc_id[u]].add(scc_id[v])

    dp = [-1] * len(sccs)
    max_purple = 0

    def dfs(scc):
        nonlocal dp
        if dp[scc] != -1:
            return dp[scc]
        max_red, max_blue = scc_category[scc]
        for neighbor in scc_graph[scc]:
            r, b = dfs(neighbor)
            max_red = max(max_red, scc_category[scc][0] + r)
            max_blue = max(max_blue, scc_category[scc][1] + b)
        dp[scc] = (max_red, max_blue)
        return dp[scc]

    for scc in range(len(sccs)):  # 以缩点后的DAG图中的每个点为起点进行dfs遍历, 并更新最大的宝石数量
        red, blue = dfs(scc)
        max_purple = max(max_purple, min(red, blue))

    return max_purple


if __name__ == '__main__':
    # n = int(input())
    # category = [int(c) for c in input()]
    # edges = []
    # m = int(input())
    # for _ in range(m):
    #     edges.append(tuple(map(int, input().split())))
    n = 6
    category = [0, 0, 0, 1, 1, 1]
    edges = [(0, 1), (1, 2), (3, 1), (2, 3), (2, 4), (2, 5)]
    print(max_purple_gems(n, category, edges))  # 输出应为2

    """文件读取"""
    with open("../../data/2022_g.in", "r") as file:
        n = int(file.readline())
        category = [int(c) for c in file.readline() if c != '\n']
        edges = []
        m = int(file.readline())
        for _ in range(m):
            edges.append(tuple(map(int, file.readline().split())))

    print(max_purple_gems(n, category, edges))  # 79
